package com.gitee.wsl.ext.array.sort

import com.gitee.wsl.ext.array.findMinimumIndex
import com.gitee.wsl.ext.array.swap

/**
 * Selection sort is a simple comparison-based sorting algorithm. It works by dividing the array into a sorted
 * and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region
 * and moves it to the sorted region. The algorithm maintains two subarrays: the subarray of sorted elements
 * and the subarray of unsorted elements.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n^2)
 * Average performance:          O(n^2)
 * Worst-case space complexity:  O(1)
 */
fun<T : Comparable<T>> Array<T>.selectionSort(){
    for (i in indices) {
        val min = findMinimumIndex(i)
        if (min != i) {
            swap(min, i)
        }
    }
}


/**
 * Stable Selection Sort is a variation of the selection sort algorithm that maintains the relative order
 * of elements with equal values. It achieves this by moving the minimum element to the current position
 * and shifting the elements to the right, instead of swapping them directly.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n^2)
 * Average performance:          O(n^2)
 * Worst-case space complexity:  O(1)
 */
fun<T : Comparable<T>> Array<T>.stableSelectionSort(){
    for (i in indices) {
        var min = findMinimumIndex(i)
        for (j in i + 1 until size) {
            if (this[j] < this[min]) {
                min = j
            }
        }
        // Move minimum element at current i.
        val key = this[min]
        while (min > i) {
            this[min] = this[min - 1]
            min--
        }
        this[i] = key
    }
}


 fun<T> Array<T>.selectionSort(fromIdx: Int, toIdx: Int, comparator: Comparator<T>) {
    for (i in fromIdx until toIdx - 1) {
        var m = i
        for (j in i + 1 until toIdx) {
            if (comparator.compare(this[j], this[m]) < 0) {
                m = j
            }
        }
        if (m != i) {
            this.swap(i, m)
        }
    }
}